package 链表;

import sun.rmi.runtime.NewThreadAction;

// 首先找出 链表的总个数k，要翻转n次
// 进行头插逆序 n 次，得到结果
// 指针的运用：  cur跟随指针跳动 tmp是指向链表最后一个 arr负责指向剩余的链表
// 然后把后面不需要逆序的部分连上
public class K个一组翻转链表 {
    static  class  ListNode{
        int val;
        ListNode prev;
        ListNode next;
        ListNode(int val){
            this.val=val;
        }
        ListNode(int val,ListNode next){
            this.val = val;
            this.next = next;
        }
    }
    public ListNode reverseKGroup(ListNode head, int k) {
        // 1.先求出需要逆序多少组  n
            ListNode cmd= head;
             int n = 0;
         while(cmd!=null){
             cmd = cmd.next;
             n++;
         }
         n /=k;
         // 2. 重复n次，长度为 k的链表的逆序
            ListNode newhead = new ListNode(0);
           ListNode cur = head;
            ListNode prev = newhead;  //保持newhead独立性
           for(int i = 1 ; i<=n;i++){
                ListNode tmp = cur;//保留当前的节点
               for(int c = 1;c<=k;c++){  // 头插
                   ListNode next = cur.next;
                   cur.next = prev.next;
                   prev.next = cur;
                   cur = next;
               }
               prev = tmp; // 将进入下一组链表的准备

           }
        //把不需要的逆序的部分连接上
        prev.next = cur;
        return newhead.next;

    }

    public static void main(String[] args) {
        K个一组翻转链表 z = new K个一组翻转链表();
        ListNode head5 = new ListNode(5,null);
        ListNode head4 = new ListNode(4,head5);
        ListNode head3 = new ListNode(3,head4);
        ListNode head2 = new ListNode(2,head3);
        ListNode head1 = new ListNode(1,head2);

        int k = 2;
        z.reverseKGroup(head1,k);
    }

}
